#include <vector>
#include <stdlib.h>

template <typename T>
class UnionFindSet
{
public:
    UnionFindSet(size_t n):
        _ufs(n, -1)
    {}
    int FindRoot(int index)
    {
        for(; _ufs[index] >= 0;)
        {
            index = _ufs[index];
        }
        return index;
    }
    bool Union(int i1, int i2)
    {
        int root1 = FindRoot(i1);
        int root2 = FindRoot(i2);
        if(root1 == root2) return false;
        else if(_ufs[root1] > _ufs[root2])
        {
            std::swap(root1, root2);
        }
        _ufs[root1] += _ufs[root2];
        _ufs[root2] = root1;
        return true;
    }
    int Size()
    {
        int size = 0;
        for(auto e : _ufs)
        {
            if(e < 0) size++;
        }
        return size;
    }

private:
    std::vector<T> _ufs;
};
